#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <algorithm>
#include <unordered_set>
using namespace std;

// 1. 基本DFS：图的遍历
class GraphDFS {
public:
    void dfsRecursive(vector<vector<int>>& graph, int node, vector<bool>& visited) {
        visited[node] = true;
        cout << node << " ";
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                dfsRecursive(graph, neighbor, visited);
            }
        }
    }
    
    void dfsIterative(vector<vector<int>>& graph, int start) {
        stack<int> stk;
        vector<bool> visited(graph.size(), false);
        
        stk.push(start);
        
        cout << "迭代DFS遍历顺序: ";
        while (!stk.empty()) {
            int node = stk.top();
            stk.pop();
            
            if (visited[node]) continue;
            
            visited[node] = true;
            cout << node << " ";
            
            // 将邻居加入栈（注意顺序）
            for (int i = graph[node].size() - 1; i >= 0; i--) {
                int neighbor = graph[node][i];
                if (!visited[neighbor]) {
                    stk.push(neighbor);
                }
            }
        }
        cout << endl;
    }
};

// 2. 回溯算法：全排列
class Permutations {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        
        backtrack(nums, path, used, result);
        return result;
    }
    
private:
    void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& result) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            
            used[i] = true;
            path.push_back(nums[i]);
            backtrack(nums, path, used, result);
            path.pop_back();
            used[i] = false;
        }
    }
};

// 3. 回溯算法：组合
class Combinations {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> path;
        
        backtrack(n, k, 1, path, result);
        return result;
    }
    
private:
    void backtrack(int n, int k, int start, vector<int>& path, vector<vector<int>>& result) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        
        for (int i = start; i <= n; i++) {
            path.push_back(i);
            backtrack(n, k, i + 1, path, result);
            path.pop_back();
        }
    }
};

// 4. N皇后问题
class NQueens {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<int> queens; // queens[i] = j 表示第i行第j列放置皇后
        
        backtrack(n, 0, queens, result);
        return result;
    }
    
private:
    void backtrack(int n, int row, vector<int>& queens, vector<vector<string>>& result) {
        if (row == n) {
            result.push_back(constructBoard(queens, n));
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (isValid(queens, row, col)) {
                queens.push_back(col);
                backtrack(n, row + 1, queens, result);
                queens.pop_back();
            }
        }
    }
    
    bool isValid(vector<int>& queens, int row, int col) {
        for (int i = 0; i < queens.size(); i++) {
            if (queens[i] == col || abs(queens[i] - col) == abs(i - row)) {
                return false;
            }
        }
        return true;
    }
    
    vector<string> constructBoard(vector<int>& queens, int n) {
        vector<string> board(n, string(n, '.'));
        for (int i = 0; i < n; i++) {
            board[i][queens[i]] = 'Q';
        }
        return board;
    }
};

// 5. 岛屿数量（DFS应用）
class NumberOfIslands {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        
        int m = grid.size(), n = grid[0].size();
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        
        return count;
    }
    
private:
    void dfs(vector<vector<char>>& grid, int i, int j) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != '1') {
            return;
        }
        
        grid[i][j] = '0'; // 标记为已访问
        
        // 四个方向递归
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
};

// 6. 单词搜索（DFS + 回溯）
class WordSearch {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) return false;
        
        int m = board.size(), n = board[0].size();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
private:
    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int index) {
        if (index == word.length()) return true;
        
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || 
            board[i][j] != word[index]) {
            return false;
        }
        
        char temp = board[i][j];
        board[i][j] = '#'; // 标记为已访问
        
        bool found = dfs(board, word, i + 1, j, index + 1) ||
                    dfs(board, word, i - 1, j, index + 1) ||
                    dfs(board, word, i, j + 1, index + 1) ||
                    dfs(board, word, i, j - 1, index + 1);
        
        board[i][j] = temp; // 恢复
        return found;
    }
};

// 7. 路径总和（二叉树DFS）
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class PathSum {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        
        if (!root->left && !root->right) {
            return root->val == targetSum;
        }
        
        return hasPathSum(root->left, targetSum - root->val) ||
               hasPathSum(root->right, targetSum - root->val);
    }
    
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> result;
        vector<int> path;
        
        dfs(root, targetSum, path, result);
        return result;
    }
    
private:
    void dfs(TreeNode* root, int targetSum, vector<int>& path, vector<vector<int>>& result) {
        if (!root) return;
        
        path.push_back(root->val);
        
        if (!root->left && !root->right && root->val == targetSum) {
            result.push_back(path);
        }
        
        dfs(root->left, targetSum - root->val, path, result);
        dfs(root->right, targetSum - root->val, path, result);
        
        path.pop_back();
    }
};

// 8. 记忆化DFS：斐波那契数列
class Fibonacci {
public:
    int fib(int n) {
        vector<int> memo(n + 1, -1);
        return dfs(n, memo);
    }
    
private:
    int dfs(int n, vector<int>& memo) {
        if (n <= 1) return n;
        
        if (memo[n] != -1) return memo[n];
        
        memo[n] = dfs(n - 1, memo) + dfs(n - 2, memo);
        return memo[n];
    }
};

// 演示函数
void demonstrateDFS() {
    cout << "=== DFS算法演示 ===" << endl << endl;
    
    // 1. 基本图遍历
    cout << "1. 基本图遍历:" << endl;
    vector<vector<int>> graph = {
        {1, 2},
        {0, 3, 4},
        {0, 5},
        {1},
        {1, 5},
        {2, 4}
    };
    
    GraphDFS graphDFS;
    vector<bool> visited(graph.size(), false);
    cout << "递归DFS遍历顺序: ";
    graphDFS.dfsRecursive(graph, 0, visited);
    cout << endl;
    graphDFS.dfsIterative(graph, 0);
    cout << endl;
    
    // 2. 全排列
    cout << "2. 全排列:" << endl;
    vector<int> nums = {1, 2, 3};
    Permutations permutations;
    vector<vector<int>> perms = permutations.permute(nums);
    cout << "数组 [1, 2, 3] 的全排列:" << endl;
    for (const auto& perm : perms) {
        cout << "[";
        for (int i = 0; i < perm.size(); i++) {
            cout << perm[i];
            if (i < perm.size() - 1) cout << ", ";
        }
        cout << "]" << endl;
    }
    cout << endl;
    
    // 3. 组合
    cout << "3. 组合:" << endl;
    Combinations combinations;
    vector<vector<int>> combs = combinations.combine(4, 2);
    cout << "从1到4中选择2个数的组合:" << endl;
    for (const auto& comb : combs) {
        cout << "[";
        for (int i = 0; i < comb.size(); i++) {
            cout << comb[i];
            if (i < comb.size() - 1) cout << ", ";
        }
        cout << "]" << endl;
    }
    cout << endl;
    
    // 4. N皇后问题
    cout << "4. N皇后问题 (4皇后):" << endl;
    NQueens nQueens;
    vector<vector<string>> solutions = nQueens.solveNQueens(4);
    cout << "4皇后问题的解数量: " << solutions.size() << endl;
    if (!solutions.empty()) {
        cout << "第一个解:" << endl;
        for (const string& row : solutions[0]) {
            cout << row << endl;
        }
    }
    cout << endl;
    
    // 5. 岛屿数量
    cout << "5. 岛屿数量:" << endl;
    vector<vector<char>> grid = {
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}
    };
    NumberOfIslands islands;
    int islandCount = islands.numIslands(grid);
    cout << "岛屿数量: " << islandCount << endl << endl;
    
    // 6. 单词搜索
    cout << "6. 单词搜索:" << endl;
    vector<vector<char>> board = {
        {'A', 'B', 'C', 'E'},
        {'S', 'F', 'C', 'S'},
        {'A', 'D', 'E', 'E'}
    };
    string word = "ABCCED";
    WordSearch wordSearch;
    bool found = wordSearch.exist(board, word);
    cout << "在网格中搜索单词 \"" << word << "\": " << (found ? "找到" : "未找到") << endl << endl;
    
    // 7. 路径总和
    cout << "7. 路径总和:" << endl;
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(11);
    root->left->left->left = new TreeNode(7);
    root->left->left->right = new TreeNode(2);
    root->right->left = new TreeNode(13);
    root->right->right = new TreeNode(4);
    root->right->right->right = new TreeNode(1);
    
    PathSum pathSum;
    bool hasPath = pathSum.hasPathSum(root, 22);
    cout << "是否存在路径和为22: " << (hasPath ? "是" : "否") << endl << endl;
    
    // 8. 记忆化DFS
    cout << "8. 记忆化DFS - 斐波那契数列:" << endl;
    Fibonacci fibonacci;
    int n = 10;
    int fibResult = fibonacci.fib(n);
    cout << "第" << n << "个斐波那契数: " << fibResult << endl;
}

int main() {
    demonstrateDFS();
    return 0;
}
